|
The forking lemma is any of a number of related lemmas in cryptography research. The lemma states that if an adversary (typically a probabilistic Turing machine), on inputs drawn from some distribution, produces an output that has some property with non-negligible probability, then with non-negligible probability, if the adversary is re-run on new inputs but with the same random tape, its second output will also have the property. This concept was first used by David Pointcheval and Jacques Stern in "Security proofs for signature schemes," published in the proceedings of Eurocrypt 1996.〔Ernest Brickell, David Pointcheval, Serge Vaudenay, and Moti Yung, "(Design Validations for Discrete Logarithm Based Signature Schemes )", Third International Workshop on Practice and Theory in Public Key Cryptosystems, PKC 2000, Melbourne, Australia, January 18–20, 2000, pp. 276–292.〕〔Adam Young and Moti Yung, "Malicious Cryptography: Exposing Cryptovirology", Wiley press, 2004, pp. 344.〕 In their paper, the forking lemma is specified in terms of an adversary that attacks a digital signature scheme instantiated in the random oracle model. They show that if an adversary can forge a signature with non-negligible probability, then there is a non-negligible probability that the same adversary with the same random tape can create a second forgery in an attack with a different random oracle.〔David Pointcheval and Jacques Stern, "(Security Proofs for Signature Schemes )", Advances in Cryptology — EUROCRYPT '96, Saragossa, Spain, May 12–16, 1996, pp. 387–398.〕 The forking lemma was later generalized by Mihir Bellare and Gregory Neven.〔Mihir Bellare and Gregory Neven, "(Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma )", Proceedings of the 13th Association for Computing Machinery (ACM) Conference on Computer and Communications Security (CCS), Alexandria, Virginia, 2006, pp. 390–399.〕 The forking lemma has been used to prove the security of a variety of digital signature schemes and other random-oracle based cryptographic constructions.〔 ==Statement of the lemma== The generalized version of the lemma is stated as follows.〔 Let ''A'' be a probabilistic algorithm, with inputs (''x'', ''h''1, ..., ''h''''q''; ''r'') that outputs a pair (''J'', ''y''), where ''r'' refers to the random tape of ''A'' (that is, the random choices A will make). Suppose further that ''IG'' is a probability distribution from which ''x'' is drawn, and that ''H'' is a set of size ''h'' from which each of the ''hi'' values are drawn according to the uniform distribution. Let acc be the probability that on inputs distributed as described, the ''J'' output by ''A'' is greater than or equal to 1. We can then define a "forking algorithm" ''FA'' that proceeds as follows, on input ''x'': # Pick a random tape ''r'' for ''A''. # Pick ''h''1, ..., ''h''''q'' uniformly from ''H''. # Run ''A'' on input (''x'', ''h''1, ..., ''h''''q''; ''r'') to produce (''J'', ''y''). # If ''J'' = 0, then return (0, 0, 0). # Pick ''h'J, ..., h'q'' uniformly from ''H''. # Run ''A'' on input (''x'', ''h''1, ..., ''h''''J''−1, ''h'' # If ''J' '' = ''J'' and ''hJ'' ≠ ''h'J'' then return (1, ''y'', ''y'' Let frk be the probability that ''FA'' outputs a triple starting with 1, given an input ''x'' chosen randomly from ''IG''. Then : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「forking lemma」の詳細全文を読む スポンサード リンク
|